/*
 * @Author: xujianwei
 * @Date: 2021-11-15 15:07:09
 * @LastEditors: xujianwei
 * @LastEditTime: 2021-11-18 16:49:48
 */

// * 快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
// 1. 从数列中挑出一个元素，称为 “基准”（pivot）；
// 2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
// 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。


// 递归方法，存在一定的限制，大量数据存在问题
const quickSort = function(arr) {
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
    let eq = 0
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else if(arr[i] >pivot) {
　　　　　　right.push(arr[i]);
　　　　}else{ // 兼容重复数据较多情况
            eq++
        }
    }
　　return quickSort(left).concat([pivot,Array(eq).fill(pivot)], quickSort(right));
};

export default quickSort;

// 数组交换位置
function swap(arr, i1, i2) {
    const temp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = temp;
}
  
/**
 * 对指针进行移动，找到最后指针所指向的位置
 * @param {*} arr  数组
 * @param {*} p  起始下标
 * @param {*} r  结束下标
 */
function divide(arr, begin, end) {
    let point = begin - 1; 
    for (let j = begin; j < end; j++) {
        if (arr[j] <= arr[end]) { 
              // 如果比基准点小就指针++，然后交换元素位置
            point++;
            swap(arr, point, j);
        }
    }
    swap(arr, point + 1, end);
    return point + 1;
}
  let index = 0
/**
 * 
 * @param {*} arr  数组
 * @param {*} begin  起始下标
 * @param {*} end  结束下标
 */

function qs(arr, begin = 0, end) {
    end = end || arr.length -1;
    let list = [[begin,end]]
    while(list.length){
        let [begin,end] = list.shift()
        const index = divide(arr, begin, end);
        if(begin< index -1)list.push([ begin, index -1])
        if(index + 1< end)list.push([ index + 1, end])
        
    }
    return arr;
}